236

Bioinformatics of the Brain

FIGURE 9.6

Some motifs of three nodes found in brain networks.

are depicted in Figure 9.6 as re-organization of 3-node motifs during loss and

recovery of consciousness is explored in [14].

Motifs of a brain network may be discovered using either network-centric

or motif-centric methods. All subgraphs of given size are searched in network-

centric methods whereas the motif mk of size k is input to a motif-centric

method. Evaluation of motifs in a given network involves implementation of

the following steps:

1.

Motif Discovery: Motifs can be found either by exact counting meth-

ods which require high computational times, or by sampling in

which random small samples from the large complex graph may

be extracted and motifs search is carried in these samples. The re-

sults obtained are then projected to the whole graph to estimate its

overall structure.

2.

Isomorphic Classes: Motifs of equivalent isomorphic class found are

placed in the same group to simplify processing since they are of

the same structure.

3.

Statistical Significance: The evaluation of the discovered motifs is

performed in this step, commonly by generating a set of random

graphs of similar structures to the original graph and applying the

above two steps to this set. Then, statistical significance of the dis-

covered motifs in both cases is evaluated to determine the validity

of the motifs found in the original graph.

Two main methods of motif search are network-centric and motif-centric.

All subgraphs of size k is searched in the former and a certain motif mk of size

k is investigated in the latter. Statistical significance of the discovered motifs

can be evaluated using P-score, Z-score or motif significance profile [6].

9.5.2

Motifs of the Brain Networks

Detection of motifs which are recurring subgraph patterns in connectome may

provide crucial information on the functioning of the human brain. These

motifs are assumed to perform some important function whereas infrequent

subgraph patterns across a number of connectomes may be associated with

individual variability.

DotMotif is a tool that combines graph database and analysis libraries pro-

viding a query interface to search subgraphs in connectome [15]. The authors